#ifndef _SKIPLIST_H
#define _SKIPLIST_H

#include <iostream>
#include <memory>

#include "Node.h"
#include "RandomLevel.h"

// use templates to use static polimorphism for typesafety
template<class KeyType = int, class ValueType = int, unsigned MaxLevel = 5, unsigned RandomProbability = 2>
class Skiplist
{
public:
	Skiplist(void) : head()
	{
		std::cout << RandomLevel<MaxLevel, RandomProbability>::randomLevel() << std::endl;
	}
    
	~Skiplist(void)
	{
        
	}
	/*
	 * returns the node with the given ValueType
     */
	ValueType search(KeyType key)
	{
		Node<KeyType, ValueType> x;
		setInsertPosition(key, &x);
        
		x = x.getNextNode(0);
		if(x.mKeyValuePair.first == key)
			return x.mKeyValuePair.second;
		
		return NULL;
	}
	/*
	 * finds last node in list which has a smaller keyValue than the searched keyValue and sets it to x
     */
	void setInsertPosition(KeyType key, Node<KeyType, ValueType> &x)
	{
		x = head->get();
		unsigned int currentLevel = MaxLevel;
        
		for(int i=currentLevel; i > 0; i--)
		{
			while(x.getNextNode(i) < key)
				x = x.getNextNode(i);
		}
		
	}
	
	/*
	 * inserts given node to skiplist
     */
	void insert(KeyType key, ValueType value)
	{
		Node<KeyType, ValueType> x;
		setInsertPosition(key, &x);
        
		unsigned int randomHeight = RandomLevel<MaxLevel, RandomProbability>::randomLevel();
		Node<KeyType, ValueType> *newNode = new Node<KeyType, ValueType>(key, value, randomHeight);
        
		//update pointer
		updatePointer(x, newNode, 0);
		for(int i=randomHeight; i > 0; i--)
		{
			x = head->get();
            
			while(x.getNextNode(i) < key)
				x = x.getNextNode(i);
            
			updatePointer(x, newNode, 0);
		}
	}
    
	void updatePointer(Node<KeyType, ValueType> &nodeInFront, Node<KeyType, ValueType> &newNode, unsigned int level)
	{
		newNode.mNext[level] = nodeInFront.mNext[level];
		nodeInFront.mNext[level] = newNode;
	}
	
	/*
	 * inserts given ValueType to skiplist
     */
	void remove(KeyType key);
	
	/*
	 * clears the skiplist and delets all the nodes
     */
	void clear();
private:
	std::tr1::shared_ptr<Node<KeyType, ValueType> > head;
};

#endif /* _SKIPLIST_H */